//
// Created by francklinson on 2021/7/25 AT 9:24.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>> &costs) {
        /**
         * 我们这样来看这个问题，公司首先将这 2N 个人全都安排飞往 B 市，
         * 再选出 N 个人改变它们的行程，让他们飞往 A 市。
         * 如果选择改变一个人的行程，那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负。
           因此最优的方案是，选出 price_A - price_B 最小的 N 个人，让他们飞往 A 市，其余人飞往 B 市。
         */
        // 按照priceA- priceB 排序
        sort(costs.begin(), costs.end(), [](vector<int> &planA, vector<int> &planB) {
            return planA[0] - planA[1] < planB[0] - planB[1];
        });
        auto N = costs.size() / 2;
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            // 最小的N个人去A，大的N个人的去B
            ans += costs[i][0] + costs[i + N][1];
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> costs{{259, 770},
                              {448, 54},
                              {926, 667},
                              {184, 139},
                              {840, 118},
                              {577, 469}};
    Solution solution;
    cout << solution.twoCitySchedCost(costs) << endl;
    return 0;
}

